package swardToOffer.method_1_recurse_or_iteration;

/**
 * @Author ChanZany
 * @Date 2021/5/20 10:21
 * @Version 1.0
 */
public class Fibonacci {
    public int func1(int n) {
        int[] a = new int[n+1];
        a[0] = 0;
        a[1] = 1;
        for (int i = 2; i <= n; i++) {
            a[i] = a[i - 1] + a[i - 2];
        }
        return a[n];
    }

    //观察到上面的方法中真正对结果有用的是n-1和n-2项，不妨通过更新这两项来节省o(n)的空间开销
    public int func2(int n) {
        if (n==0||n==1) return n;
        int a = 0;
        int b = 1;
        int res = 0;
        for (int i = 2; i <= n; i++) {
            res = a+b;//a[i]->a[i+1]=a[i]+a[i-1]
            a = b; //a[i-1]
            b = res;//a[i]
        }
        return res;
    }

    public static void main(String[] args) {
        Fibonacci Main = new Fibonacci();
        System.out.println(Main.func1(2));
        System.out.println(Main.func1(3));
        System.out.println(Main.func1(4));
        System.out.println(Main.func1(5));
        System.out.println("---------------------");
        System.out.println(Main.func2(2));
        System.out.println(Main.func2(3));
        System.out.println(Main.func2(4));
        System.out.println(Main.func2(5));
    }
}
